"""
题目：判断一个无向图是否为连通图（所有顶点之间都有路径）。
整体逻辑总结该方法通过DFS遍历从一个顶点出发，尝试访问所有可达的顶点，最后通过比较 “已访问顶点数” 和 “总顶点数”，判断图是否为连通图。
时间复杂度为(O(V + E))（V是顶点数，E是边数），是判断无向图连通性的经典高效方法。
"""


class Graph:
    def __init__(self, is_directed=False):
        #vertices是一个字典，key是顶点，value是该顶点对应的所有的邻接点的集合(list)
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        #如果之前没有添加过，则添加
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        #加边之前要先把顶点加入该图，有顶点才会有边
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        #如果是无向图，则对称的另一面也要添加上
        if not self.is_directed:
            self.vertices[v2].append(v1)

    """判断无向图是否为连通图"""
    def is_connected(self):
        if not self.vertices:  # 空图视为连通
            return True
        # 从任意一个顶点开始遍历
        #self.vertices.keys() 获取所有顶点的集合，iter() 将其转换为迭代器，next() 取出第一个顶点作为遍历的起点。
        #因为是无向图，从任意顶点开始遍历的结果都能反映图的连通性。
        start_vertex = next(iter(self.vertices.keys()))
        #visited为什么用 set 而非 list？
        # 核心区别的核心在 x in visited 操作的时间复杂度：
        # set 的 in 操作：时间复杂度为 O(1)（平均情况），因为 set 基于哈希表实现，查找元素无需遍历。
        # list 的 in 操作：时间复杂度为 O(n)（n 是列表长度），因为需要从头部到尾部逐个比对元素。
        visited = set()
        # DFS遍历所有可达顶点
        def dfs(vertex):
            visited.add(vertex)
            for neighbor in self.vertices[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)
        dfs(start_vertex)
        # 如果所有顶点都被访问，则图是连通的
        return len(visited) == len(self.vertices)
# 测试
# 连通图
graph1 = Graph()
graph1.add_edge(1, 2)
graph1.add_edge(2, 3)
graph1.add_edge(3, 4)
print(graph1.is_connected())  # 输出: True

# 非连通图（两个独立分量）
graph2 = Graph()
graph2.add_edge(1, 2)
graph2.add_edge(3, 4)  # 3和4与1和2没有连接
print(graph2.is_connected())  # 输出: False
